#ifndef __FLOYDWARSHALL__
#define __FLOYDWARSHALL__
#include <limits>
#include <iostream>
#define MAX_NODE_NUM 100
#define MAX_WEIGHT std::numeric_limits<int>::max()

int weight[MAX_NODE_NUM][MAX_NODE_NUM];
int shortest[MAX_NODE_NUM][MAX_NODE_NUM];
int father[MAX_NODE_NUM][MAX_NODE_NUM];

void FloydWarshall(int weight[][MAX_NODE_NUM], int len){
	for(int i = 0 ; i < len; ++i)
		for(int j = 0; j < len; ++j)
			shortest[i][j] = weight[i][j];

	for(int k = 0; k < len; ++k)
		for(int i = 0; i < len; ++i)
			for(int j = 0; j < len; ++j){
				if(i != j && shortest[i][k] != MAX_WEIGHT && shortest[k][j] != MAX_WEIGHT){
					int weight = shortest[i][k] + shortest[k][j];
					if(weight < shortest[i][j]){
						shortest[i][j] = weight;
						father[i][j] = father[k][j];
					}
						
					
				}
			}
}

void Test(){
	for(int i = 0; i < 5; ++i)
		for(int j = 0; j < 5; ++j){
			if(i != j)
				weight[i][j] = MAX_WEIGHT;
			else
				weight[i][j] = 0;
		}

	weight[0][1] = 3; weight[0][2] = 8; weight[0][4] = -4;
	weight[1][4] = 7; weight[1][3] = 1;
	weight[2][1] = 4;
	weight[3][2] = -5; weight[3][0] = 2;
	weight[4][3] = 6;

	for(int i = 0; i < 5; ++i)
		for(int j = 0; j < 5; ++j)
			if(weight[i][j] != MAX_WEIGHT && weight[i][j] != 0)
				father[i][j] = i+1;
			else
				father[i][j] = MAX_NODE_NUM;

	FloydWarshall(weight, 5);
}
#endif